package NewCoder;

public class BM90 {
    public String minWindow (String S, String T) {
        // write code here
        if(S.length()==0 || T.length()==0 || S.length()<T.length()) return "";
        int[] wFreq=new int[128];//s的子串的字频数组
        int[] tFreq=new int[128];//t的子串的字频数组
        char[] sc=S.toCharArray();
        char[] tc=T.toCharArray();
        int distance=0;
        int begin=0;
        int len=Integer.MAX_VALUE;
        int i=0;
        int j=0;
        for(int k=0;k<T.length();k++){
            tFreq[tc[k]]++;
        }
        while(j<S.length()){
            if(tFreq[sc[j]]==0){
                j++;
                continue;
            }
            if(wFreq[sc[j]]<tFreq[sc[j]]){
                distance++;

            }
            wFreq[sc[j]]++;
            j++;

            while(distance==tc.length){
                if(j-i<len){
                    len=j-i;
                    begin=i;
                }
                if(wFreq[sc[i]]==0){
                    i++;
                    continue;
                }
                if(wFreq[sc[i]]==tFreq[sc[i]]){
                    distance--;
                }
                wFreq[sc[i]]--;
                i++;
            }
        }
        if(len==Integer.MAX_VALUE){
            return "";
        }
        return S.substring(begin,begin+len);
    }
}
